def merge_sort(nums):
            if len(nums)<=1:
                return nums,0
            mid = len(nums)//2
            left,left_count = merge_sort(nums[:mid])
            right,right_count = merge_sort(nums[mid:])
            sorted_nums,merge_count = merge(left,right)
            return sorted_nums,merge_count + left_count + right_count
def merge(left,right):
        i,j = 0,0
        count = 0
        merged = []
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                merged.append(left[i])
                i+=1
            else:
                merged.append(right[j])
                j+=1
                count +=len(left)-i
        merged+=left[i:]
        merged+=right[j:]

        return merged,count

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums:List[int]
        :rtype:int
        :param nums:
        :return:
        """
        count = 0
        result = None
        for num in nums:
            if count == 0:
                result = num
            count += (1 if result == num else -1)
        return result



from typing import List

num = eval(input("请输入n型矩阵的n为："))
matrix=[]
list = []
x = 0
y = 0
while y < num:
    print(f"请输入矩阵第{y}行的数：")
    while x < num:
        value=eval(input())
        list.append(value)
        x +=1
    matrix.append(list)
    y+=1
    x=0
    list=[]

print(matrix)
target = eval(input("请输入要查找的数?"))

def searchMatrix( matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    print(m,n)
    x, y = m - 1, n - 1
    while x >= 0 and y >= 0:
        if matrix[x][y] == target:
            print(f"{target}查到")
            return True
        elif matrix[x][y] > target:
            x -= 1
        else:
            y -= 1

    print(f"{target}查不")
    return False

searchMatrix(matrix,target)



class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def quickselect(start,end,nums,k):
            if start == end:
                return nums[start]
            mid = partion(start,end,nums)
            if mid == len(nums)-k:
                return nums[mid]
            elif mid < len(nums)-k:
                return quickselect(mid+1,end,nums,k)
            elif mid > len(nums)-k:
                return quickselect(start,mid-1,nums,k)
        def partion(start,end,nums):
            p = random.randrange(start,end+1)
            pivot = nums[p]
            nums[end],nums[p] = nums[p],nums[end]
            mid = start
            for i in range(start,end):
                if nums[i] <= pivot:
                    nums[i],nums[mid] = nums[mid],nums[i]
                    mid += 1
            nums[mid],nums[end] = nums[end],nums[mid]
            return mid
        res = quickselect(0,len(nums)-1,nums,k)
        print(res)
        return res
        a = [3 ,1 ,4 ,6 ,2 ,5]
        findKthLargest(self, a, 2)


def reversePairs( nums):
    List,ans=merge_sort(nums)
    return ans

def merge( left, right,leftn,rightn):  # 合并两个列表
    result = []
    i, j = 0, 0
    n=0
    while i < len(left) and j < len(right):
        if left[i] > 2 * right[j]:
            n += len(left)-i
            j += 1
        else:
            i += 1
    i=0
    j=0
    while i < len(left) and j < len(right):  # 左右列表分别进行归并，肯定有一个列表先归并完
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]  # 归并左子列表剩余元素
    result += right[j:]  # 归并右子列表剩余元素
    return result,n+rightn+leftn

def merge_sort( arr):
    if len(arr) <= 1:
        return arr,0
    mid = len(arr) // 2
    left ,leftn= merge_sort(arr[:mid])
    right,rightn = merge_sort(arr[mid:])
    return merge(left, right,leftn,rightn)

##
##逆序对
def reversePairsn( nums):
    List,ans=merge_sortn(nums)
    return ans
def merge_sortn(nums):
    if len(nums) <= 1:
        return nums, 0
    mid = len(nums) // 2
    left, left_count = merge_sortn(nums[:mid])
    right, right_count = merge_sortn(nums[mid:])
    sorted_nums, merge_count = mergen(left, right)
    return sorted_nums, merge_count + left_count + right_count


def mergen(left, right):
    i, j = 0, 0
    count = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            count += len(left) - i
    merged += left[i:]
    merged += right[j:]
    return merged, count

##
##
def majorityElement(nums):
    count = 0
    result = None
    for num in nums:
        if count == 0:
            result = num
        count += (1 if result == num else -1)
    return result

##
##
import random
def findKthLargest(nums, k):
    def quickselect(start, end, nums, k):
        if start == end:
            return nums[start]
        mid = partion(start, end, nums)
        if mid == len(nums) - k:
            return nums[mid]
        elif mid < len(nums) - k:
            return quickselect(mid + 1, end, nums, k)
        elif mid > len(nums) - k:
            return quickselect(start, mid - 1, nums, k)

    def partion(start, end, nums):
        p = random.randrange(start, end + 1)
        pivot = nums[p]
        nums[end], nums[p] = nums[p], nums[end]
        mid = start
        for i in range(start, end):
            if nums[i] <= pivot:
                nums[i], nums[mid] = nums[mid], nums[i]
                mid += 1
        nums[mid], nums[end] = nums[end], nums[mid]
        return mid

    res = quickselect(0, len(nums) - 1, nums, k)
    return res


def searchMatrix( matrix, target) -> bool:
    m, n = len(matrix), len(matrix[0])
    x, y = m - 1, n - 1
    while x >= 0 and y >= 0:
        if matrix[x][y] == target:
            return True
        elif matrix[x][y] > target:
            x -= 1
        else:
            y -= 1
    return False